1. Field of the Invention
The present invention relates to improving the performance of floating point execution units in a processor. More particularly, the present invention provides a method and apparatus that anticipates the need to round the result of a floating point operation, and performs that rounding in parallel with normalization process.
2. Description of the Related Art
Within a processor, arithmetic operations may be performed on operands stored in a format known as floating point. An American national standard has been developed in order to provide a uniform system of rules for governing the implementation of floating point arithmetic systems. This standard is identified as ANSI/IEEE Standard No. 754-1985, and is incorporated by reference in this application. As discussed in further detail below, ANSI/IEEE 754-1985 includes rules for representing and storing floating point operands, rules for manipulating them to perform arithmetic operations, and rules for rounding and expressing the result of the arithmetic operations(s).
According to the standard, the typical floating point arithmetic operation may be accomplished in single precision, double precision, or extended precision format. Each of these formats utilizes a sign, exponent, and fraction field, where the respective fields occupy predefined portions of the floating point number. In addition, the extended precision format includes a mantissa field, which includes the fraction field plus an additional bit, the L bit, that is merely implied in the single- and double-precision formats.
The L bit is created by control logic when the exponent of the floating point number has a nonzero value. The L bit is written into the arithmetic registers in first bit position to the left of the fraction field of floating point numbers expressed in the extended precision format. For single- and double precision floating point numbers that have non-zero exponents, the L bit is not explicitly represented in the IEEE representation, but rather, is understood by the control logic to be present and to have a value of 1.
FIG. 1 illustrates the IEEE format for a 32-bit single precision number where the sign field is a single bit occupying the most significant bit position; the exponent field is an 8-bit quantity occupying the next-most significant bit positions; and the fraction field occupies the least significant 23 bit positions. In the case of a double precision floating point number, the sign field is a single bit occupying the most significant bit position; the exponent field is an 11-bit field occupying the next-most significant bit positions; and the fraction field is a 52-bit field occupying the least significant position. The format of the extended precision floating point number requires a single sign bit, a 15 bit exponent field, and a 64-bit mantissa field that includes the fraction and the L bit.
After each floating point intermediate arithmetic result is developed, it must be normalized and rounded if a round control bit is set. Normalization refers to the process of manipulating the exponent and fraction of an unnormalized intermediate floating point result so that the most significant binary xe2x80x9c1xe2x80x9d of the mantissa resides in the L bit, which is the most significant bit of the mantissa. The exponent is decremented for each 1-bit left-shift of the mantissa.
To implement the rounding rules required by ANSI/IEEE standard 745-1985, certain additional indicator bits may be set by the floating point logic during arithmetic operations. These bits generally indicate a loss of precision of a floating point number, such as might occur when an operand is right-shifted to align it for addition and one or more bits are shifted off the right side of the register. These lost precision bits are known as the xe2x80x9cguardxe2x80x9d bit G, a xe2x80x9croundxe2x80x9d bit R, and a xe2x80x9cstickyxe2x80x9d bit S. The G and R bits are treated as if they are a part of the fraction; they are shifted with the rest of the fraction during alignment and during normalization, and they are included in all arithmetic operations. The S bit is not shifted with the fraction but is included in the arithmetic. It acts as a xe2x80x9ccatcherxe2x80x9d for 1""s shifted off the right of the fraction. When a 1 is shifted off the right side of the fraction, the S bit will remain set until normalization and rounding are finished. Setting, interpreting, and using the G, R, and S bits to create a round control bit or a signal indicating whether or not rounding is required is well known in the art.
ANSI/IEEE standard 745-1985 requires that floating point units implement a minimum of four different rounding modes and to select which rounding mode is appropriate for various floating point operations. The four different rounding approaches are (1) round-to-nearest, wherein numbers having lost precision greater than xc2xd of their least significant bit are rounded up, numbers having lost precision less than xc2xd of their least significant bit are rounded down, and numbers having lost precision equal to xc2xd of their least significant bit are rounded either up or down, to ultimately achieve an even number (i.e., to end in zero); (2) round-toward-positive-infinity, wherein numbers are always rounded up if positive and down if negative; (3) round-toward-negative-infinity, wherein numbers are always rounded down if positive and up if negative; and (4) round-toward-zero, wherein the lost precision bits are always truncated. Notably, the implementation of modes 1, 2, and 3 always requires a method or means to locate and increment the bit that occupies the round increment position of the normalized intermediate result. Incrementing this bit may then ripple through the higher-order-bits in the intermediate result to produce the final, normalized, rounded result.
A typical independent floating point unit 10 having a multiply unit 12 that is completely separate from the add unit 14 is shown in FIG. 2A. In the FIG. 2A addition unit 14, one of two input operands A and B may first be shifted in the Aligner 16, and then added together in the Adder 18 to produce an unnormalized intermediate result (A+B). This intermediate result is then passed to a leading zero/one detector (LZD)20 which produces shift control signals for the normalizer 22. The normalizer 22 produces a normalized intermediate result by shifting the unnormalized mantissa result left by an amount specified by the LZD shift control signals. The exponent is decremented by one for each bit position that the mantissa is shifted to the left until the most significant bit position of the mantissa (the leading bit) becomes a one. The rounder 24 increments the normalized intermediate result, which is then typically passed to a multiplexer 26, where either the incremented result or the non-incremented result is selected to produce the final result, depending upon the ANSI/IEEE standard 745-1985 rounding scheme appropriate for the operation.
In prior art floating point units, as shown in FIG. 2A, normalization and rounding have usually been performed sequentially. This causes the latency of the execution, pipeline to include the full delay of both the normalizer and rounder circuits. In an effort to improve floating point performance, designers have employed various techniques to reduce the latency of the floating point execution pipeline, including anticipating the need for rounding (xe2x80x9cearly roundingxe2x80x9d) and executing rounding in parallel with normalization (xe2x80x9cparallel normalization and roundingxe2x80x9d). For example, U.S. Pat. No. 4,562,553 to Mattedi et al. and U.S. Pat. No. 5,390,134 to Heikes et al. both describe an early round technique. U.S. Pat. No. 5,550,768 to Ogilvie et al. utilizes a parallel normalization and rounding technique. Parallel normalization and rounding techniques are also more fully described in a copending patent application, U.S. patent application Ser. No. 09/120,775, filed Jul. 22, 1998 (22.07.1998), now U.S. Pat. No. 6,185,593, entitled xe2x80x9cMethod and Apparatus for Parallel Normalization and Rounding Technique for Floating Point Arithmetic Operationsxe2x80x9d, which is incorporated by reference into this disclosure.
These techniques do improve the performance of independent (non-multiply-add) multiply and add pipelines, because they eliminate the majority of the rounding delay. However, they have not proven useful in fused multiply-add floating point execution units such as the fused multiply-add floating point execution unit shown in FIG. 2B, primarily because predicting the location that the round increment bit will occupy after the intermediate result is normalized is much more difficult in a fused multiply-add floating point unit.
Both the early rounding technique and the parallel normalization and rounding technique require that the approximate location (one of three positions) of the round increment position be known prior to normalization. In both techniques, the round increment position can be relatively easily determined because in independent (non-multiply-add) multiply and add pipelines, the unnormalized intermediate mantissa result for floating point arithmetic operations will always be in one of the following four possible formats:
(1) 1.XXX..XX
(2) 0.1XXX..XX
(3) 0.0XXX..XX
(4) 1X.XXX..XX
In the first format, normalization is not required since the most significant bit position of the mantissa (the leading bit) is a one. Rounding may be required. In the second format, a 1-bit shift left is required to normalize the mantissa. Rounding may be required. The third format can only be achieved as a result of an effective subtract operation where the difference between the exponents of the two operands was zero or one. If there was no shifting for alignment (because the exponents were equal) then G=R=S=0 for both operands. If the lesser operand was shifted right one position for alignment (as would be the case where the exponent of the lesser operand was one less than the exponent of the greater operand), only the G bit could be set, if the least significant bit of the lesser operand was 1. Since a minimum 2-bit shift left is required for normalizing an intermediate result in format three, the guard bit (G) will be forced to zero as zeros are shifted into the R bit. When G=R=S=0, then the normalized intermediate result is exact and rounding is not possible regardless of the rounding mode. Therefore, rounding is never required for intermediate results in format three.
Conceptually, the fourth format requires a 1-bit right shift. Format four does not actually require normalization, but rounding may be required. Therefore, of the four possible formats, only the first, second and fourth may require rounding. Each of these formats dictates a unique round increment position because the shift for normalization is known and constant. Consequently, there are only three possible round increment positions for every unnormalized intermediate result that requires rounding. The round increment position for any unnormalized intermediate result that requires rounding can be ascertained by examining its unnormalized format, and selecting the round increment position dictated by that format.
Unfortunately, using this technique to perform early rounding and/or parallel normalization and rounding is not practical for a conventional fused multiply-add pipeline because the approximate location of the round increment position is unknown prior to normalization. This is the case because conventional fused multiply-add pipelines use an xe2x80x9coffsetxe2x80x9d mantissa alignment method which results in a 3M+1 bit wide unnormalized intermediate mantissa result, where M is the width of the source mantissas. For example, assume a typical multiply-add operation of the type typically performed in a fused multiply-add pipelines: Axc3x97C+B. In performing this operation, operand B is always aligned to the Axc3x97C product. The operand B alignment amount can be determined from the equation
shift_count=(Ea+Ec)xe2x88x92Eb+offset
where Ea represents the exponent of operand A, Eb represents the exponent of operand B, and Ec represents the exponent of operand C. The offset value is 55 for double precision operations. The format for a double precision unnormalized intermediate mantissa that results from an Axc3x97C+B operation performed in a fused multiply-add floating point unit is shown in FIG. 3.
A negative shift_count results in an alignment amount of 0-bits. A positive shift_count results in an alignment amount equal to shift_count. To illustrate, if a multiply-add operation (Axc3x97C+B) is executed and Eb is equal to or greater than (Ea+Ec)+offset, the B operand mantissa will align such that it resides exactly within the most significant M-bits of the unnormalized intermediate mantissa data format because the resulting shift_count will be zero or negative, forcing an alignment amount of 0-bits. In this case the offset method prevents any overlap between operand B and the Axc3x97C product. If Eb=(Ea+Ec) the offset alignment method will align the operand B mantissa such that its radix point is exactly positioned with the Axc3x97C product radix point. If (Ea+Ec)=11 and Eb=1 then the alignment amount is calculated to be 10+offset. Due to the offset value (55 for double precision operations) many leading zeros may exist in an unnormalized intermediate result even if rounding is possible. Unlike the independent floating point add pipeline, the fused multiply-add pipeline does not produce an unnormalized intermediate result that requires rounding, where there are only three normalization shift possibilities, and therefore, only three possible round increment positions. The number of possible round increment positions for a fused multiply-add pipeline is greater than the offset (55 for double precision operations).
The present invention is a rounding anticipator method and apparatus that can be used in any floating point execution unit, but is especially useful in fused multiply-add floating point execution units where prior techniques to eliminate or reduce the delay of the rounder have not proven useful. The present invention includes a 53-bit incrementer for anticipatory rounding that employs a fast carry propagate technique known as carry lookahead. The 53-bit incrementer used in the present invention is implemented in four levels of N-NARY logic, three of which operate in parallel with the normalizer. This results in an effective latency of the present invention rounding anticipator of only one logic level.
The present invention accepts data from the coarse, medium, and fine shift functions of the normalizer to develop a normalized and incremented intermediate result, which is then selected or not selected, depending upon the normalized result and the rounding scheme appropriate for the operation.
NARY logic is described in a copending patent application, U.S. patent application Ser. No. 09/19355, filed Feb. 5, 1998, now U.S. Pat. No. 6,066,965, and titled xe2x80x9cMethod and Apparatus for a N-NARY logic Circuit Using 1 of 4 Signalsxe2x80x9d, (hereafter, xe2x80x9cthe N-NARY Patentxe2x80x9d). As described in the N-NARY Patent, N-NARY logic uses a bundle of N wires routed together between different logic circuits, where information is encoded in the N wires, and where at most one and only one wire of the bundle of wires is true during an evaluation cycle. For example, a 1-of-4 N-NARY signal is a bundle of 4 wires that is capable of being encoded to represent 4 different values, and where at most, only one wire within the 4-wire bundle is true during an evaluation cycle. As explained in the N-NARY patent, a 1-of-4 N-NARY signal C, which comprises output wires C3, C2, C1, and C0 can be encoded to represent two boolean bits A and B, as follows:
The 53-bit incrementer that comprises the rounding anticipator of the present invention incorporates basic N-NARY design principals described in the N-NARY Patent, and fast carry propagate techniques implemented in N-NARY logic in a 32-bit N-NARY incrementer described in U.S. patent application Ser. No. 09/206,830, filed Dec. 7, 1998 (07.12.1998), now U.S. Pat. No. 6,347,327, entitled xe2x80x9cMethod and Apparatus for N-NARY Incrementerxe2x80x9d (hereafter, xe2x80x9cthe Incrementer Patentxe2x80x9d). As described in the Incrementer Patent, carries propagate across a given dit only if that dit equals 3 when encoded in N-NARY logic, and will propagate across a block of dits only if all dits equal 3. For illustrative purposes only, FIG. 4 shows the conventional 32-bit N-NARY incrementer disclosed in the Incrementer Patent. Those unfamiliar with the workings of the conventional 32-bit N-NARY incrementer, including the methodologies for processing and resolving speculative propagate signals, are encouraged to refer to that patent for a complete understanding of the fast carry techniques described there and utilized in the present invention. In addition, the Incrementer Patent also provides a complete description of the xe2x80x9cshorthandxe2x80x9d N-NARY notation that is used herein to depict the various gates implemented in the present invention in N-NARY logic. Both the N-NARY Patent and the Incrementer Patent are hereby incorporated by reference into this disclosure for all purposes.
The present invention comprises a method and apparatus that performs anticipatory rounding of intermediate results in a floating point arithmetic system while the intermediate results are being normalized by a normalizer that includes coarse, medium, and fine shifting. One embodiment of the present invention includes four logic levels, implemented in N-NARY logic. In the first logic level, coarse propagation information for preselected coarse propagation bit groups is encoded from the coarse shift output from the normalizer. In the second logic level, medium propagation information for preselected medium shift bit groups is derived by combining coarse propagation information for various bit groups from Level 1, selected according to the value of the medium shift select signal from the normalizer. In the third logic level, top bit, middle bit, and bottom bit propagation information is derived for preselected top groups, middle groups, and bottom groups of bit positions of the medium shift output, as a function of the value of the fine shift select signal. This information is derived by selectively combining propagation information from the second logic level with medium shift output bit values. In the fourth logic level, an incremented, normalized intermediate single- precision or double-precision mantissa result is produced by combining fine shift output bit values with propagation information for the appropriate top bit group, middle bit group, and bottom bit group.